Originally by: Alvaliella

---

Edited by: Alvaliella on 26/11/2008 22:37:23

Originally by: Amida Ta

---

I think you are doing wrong something ;)

I am using a simple breadth-first search and even for the longest paths my application does not need longer than 0.02 seconds to calculate them.
On the other hand I'm using my EveAI data structures and no Database.

---

Any chance you could elaborate please? Granted I'm not a proper programmer but I simply can't think of how this is possible- I mean surely you have to crunch through masses of route data at some point?


Edit: Just had a thought- if you can add up the "jumps per hour" statistic over a few days for each system then that might be good to use as an A* heuristic? You'd chose whichever system had the highest number of jumps per hour (indicating that it's on a well travelled highway) rather than physical distance... it should eventually filter you onto the most commly used AutoPilot routes

---

public List<SolarSystem> FindRoute (SolarSystem start, SolarSystem end)
{
Queue<SolarSystem> openRoute = new Queue<SolarSystem> ();

start.Tag = start;
openRoute.Enqueue (start);

while (openRoute.Count > 0)
{
SolarSystem current = openRoute.Dequeue ();
if (current == end)
{
List<SolarSystem> way = new List<SolarSystem> ();
while (current != start)
{
way.Add (current);
current = (SolarSystem)current.Tag;
}
way.Add (start);
way.Reverse ();
return way;
}

foreach (SolarSystem system in current.Jumps)
{
if (system.Tag != null)
continue;
system.Tag = current;
openRoute.Enqueue (system);
}
}
return null;
}

Originally by: Ambo

---

Indeed, if I pre-load all the data I'll need then any of the methods I use will be blazingly fast.

However, loading everything into datatables when the app starts takes up too much memory and loading it all before calculating a route is too slow.

I think that my problem might be my use of the VS generated data access stuff. I'll try writing some stripped down access routines with more basic data structures and see where that gets me.

---